// MaxWeightMatching.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "MaxWeightedEdge.h"
using namespace GraphTools;

int CHECK_DELTA = true;
int CHECK_OPTIMUM = true;

MyVector<EdmondsEdge> edges;
int max_weight = 0;
MyVector<int> endpoint = MyVector<int>();
MyVector<MyVector<int>> neighbend = MyVector<MyVector<int>>();
MyVector<int> mate = MyVector<int>();
MyVector<int> label = MyVector<int>();
int nvertex = 0;
MyVector<int> labelend = MyVector<int>();
MyVector<int> inblossom = MyVector<int>();
MyVector<int> blossomparent = MyVector<int>();
MyVector<MyVector<int>> blossomchilds = MyVector<MyVector<int>>();
MyVector<int> blossombase = MyVector<int>();
MyVector<MyVector<int>> blossomdps = MyVector<MyVector<int>>();
MyVector<int> bestedge = MyVector<int>();
MyVector<MyVector<int>> blossombestedges = MyVector<MyVector<int>>();
MyVector<int> unusedblossoms = MyVector<int>();
MyVector<int> dualvar = MyVector<int>();
MyVector<boolean> allowedge = MyVector<boolean>();
MyVector<int> queue = MyVector<int>();
int nedge;

int dd(int i, int j)
{
	float i_f = (float) i;
	float j_f = (float) j;

	return (int)floorf(i_f / j_f);
}

int indexOf(MyVector<int> elems, int i)
{
	for (int idx = 0; idx < elems.size(); idx++)
	{
		if (elems[idx] == i)
			return idx;
	}
	throw "Element not found";
}

MyVector<int> take(MyVector<int> v, int i)
{
	MyVector<int> elems = MyVector<int>();
	for(int j = 0; j < i; j ++)
	{
		elems.push_back(v[j]);
	}
	return elems;
}

MyVector<int> skip(MyVector<int> v, int i)
{
	MyVector<int> elems = MyVector<int>();
	for(int j = i; j < v.size(); j ++)
	{
		elems.push_back(v[j]);
	}
	return elems;
}



int slack(int k)
{
	return (dualvar[edges[k][0]]) + (dualvar[edges[k][1]]) - (2 * edges[k][2]);
}

MyVector<int> blossomLeaves(int b)
{
	MyVector<int> lst = MyVector<int>();
	if(b < nvertex)
	{      
			lst.push_back(b);
	}
	else{
		for(int i = 0; i < blossomchilds[b].size(); i++)
		{
			int t = blossomchilds[b][i];
			if(t < nvertex)
			{
				lst.push_back(t);
			}
			else
			{
				MyVector<int> vs = blossomLeaves(t);
				for(int i = 0; i < vs.size(); i++)
				{
					lst.push_back(vs[i]);
				}
			}

		}
	}
	return lst; 
}

void assignLabel(int w, int t, int p)
{
	int b = inblossom[w];
	if(!(label[w] == 0 && label[b] == 0))
		throw "Assert Error";

	label[w] = t;
	label[b] = t;
	labelend[w] = p;
	labelend[b] = p;
	bestedge[w] = -1;
	bestedge[b] = -1;

	if(t == 1)
	{
		MyVector<int> lst = blossomLeaves(b);
		for(int i = 0; i < lst.size(); i ++)
			queue.push_back(lst[i]);
	}
	else if(t == 2)
	{
		int base = blossombase[b];
		if(!(mate[base] >=0)) throw "Assert Error";
		assignLabel(endpoint[mate[base]], 1, mate[base] ^ 1);
	}

}

int scanBlossom(int v, int w)
{
	MyVector<int> path = MyVector<int>();
	int base = -1;
	while(v != -1 || w != -1)
	{

		int b = inblossom[v];
		if (label[b] & 4)
		{
			base = blossombase[b];
			break;
		}
		if(label[b] != 1) throw "Assert Error";
		
		path.push_back(b);
		label[b] = 5;

		if(labelend[b] != mate[blossombase[b]]) throw "Assert Error";

		if(labelend[b] == -1)
		{
			v = -1;
		}
		else
		{
			v = endpoint[labelend[b]];
			b = inblossom[v];
			if(label[b] != 2) throw "Assert Error";
			if(labelend[b] < 0) throw "Assert Error";
			v = endpoint[labelend[b]];

		}
		if(w != -1)
		{
			int tmp = v;
			v = w;
			w = tmp;
		}
	}
	for(int i = 0; i < path.size(); i++)
	{
		label[path[i]] = 1;
	}
	return base;
}

void addBlossom(int base, int k) // row 359
{
	int v = edges[k][0];
	int w = edges[k][1];
	int wt = edges[k][2];

	int bb = inblossom[base];
	int bv = inblossom[v];
	int bw = inblossom[w];


	int b = unusedblossoms[unusedblossoms.size() - 1];
	unusedblossoms.pop_back();

	blossombase[b] = base;
	blossomparent[b] = -1;
	blossomparent[bb] = b;

	//MyVector<int> /*path,*/ endps;
	
	//devono andare di pari passo....
	blossomchilds[b] = MyVector<int>();
	//path = MyVector<int>();
	blossomdps[b] = MyVector<int>();

	while(bv != bb)
	{
		blossomparent[bv] = b;
		blossomchilds[b].push_back(bv);
		blossomdps[b].push_back(labelend[bv]);

		if(!(label[bv] == 2 || label[bv] == 1 && labelend[bv] == mate[blossombase[bv]])) throw "Assert Error";
		if(labelend[bv] < 0) throw "Assert Error";

		v = endpoint[labelend[bv]];
		bv= inblossom[v];
	}

	blossomchilds[b].push_back(bb);
	blossomchilds[b].reverse();
	blossomdps[b].reverse();
	//std::reverse(blossomchilds[b].begin(), blossomchilds[b].end()); 
	//std::reverse(blossomdps[b].begin(), blossomdps[b].end()); 
	blossomdps[b].push_back(2 * k);

	while(bw != bb)
	{
		blossomparent[bw] = b;
		blossomchilds[b].push_back(bw);
		blossomdps[b].push_back(labelend[bw] ^ 1);

		if(!(label[bw] == 2 || label[bw] == 1 && labelend[bw] == mate[blossombase[bw]])) throw "Assert Error";
		if(labelend[bw] < 0) throw "Assert Error row 306";

		w = endpoint[labelend[bw]];
		bw = inblossom[w];
	}

	if(label[bb] !=1) throw "Assert Error row 312";
	label[b] = 1;
	labelend[b] = labelend[bb];

	dualvar[b] = 0;

	MyVector<int> vs = blossomLeaves(b);	
	for(int vi = 0; vi < vs.size(); vi++)
	{
		int v = vs[vi];
		if(label[inblossom[v]] == 2)
			queue.push_back(v);
		inblossom[v] = b;
	}


	MyVector<int> bestedgeto = MyVector<int>();
	for(int i = 0; i < 2 * nvertex; i++)
	{
		bestedgeto.push_back(-1);
	}

	for(int i = 0; i < blossomchilds[b].size(); i++)
	{
		int bv = blossomchilds[b][i];
		MyVector<MyVector<int>> nblists = MyVector<MyVector<int>>();


		if (blossombestedges[bv].size() == 0)
		{
			MyVector<int> vs = blossomLeaves(bv);
			for(int i = 0; i < vs.size(); i++)
			{					
				nblists.push_back(MyVector<int>());
				int v = vs[i];

				for(int j = 0; j < neighbend[v].size(); j++)
				{					
					int p = neighbend[v][j];
					nblists[i].push_back(dd(p, 2)); //row 322
				}
			}
		}
		else
		{
			nblists.push_back(blossombestedges[bv]);
		}
		for(int i1 = 0; i1 < nblists.size(); i1++)
		{
			MyVector<int> nblist = nblists[i1];
			for(int j1 = 0; j1 < nblist.size(); j1++)
			{
				int k = nblist[j1];

				int i = edges[k][0];
				int j = edges[k][1];
				int wt = edges[k][2];

				if(inblossom[j] == b)
				{
					int tmp = i;
					i = j;
					j = tmp;
				}
				int bj = inblossom[j];
				if(bj != b && label[bj] == 1 && (bestedgeto[bj] == -1 || slack(k) < slack(bestedgeto[bj])))
				{
					bestedgeto[bj] = k;
				}
			}
		}
		blossombestedges[bv] = MyVector<int>();
		bestedge[bv] = -1;		
	}
	MyVector<int> ks = MyVector<int>();
	for(int i = 0; i < bestedgeto.size(); i++)
	{
		if (bestedgeto[i] != -1) ks.push_back(bestedgeto[i]);
	}
	blossombestedges[b] = ks;
	bestedge[b] = -1;

	for(int i = 0; i < blossombestedges[b].size(); i++)
	{
		int k = blossombestedges[b][i];
		if(bestedge[b] == -1 || slack(k) < slack(bestedge[b]))
		{
			bestedge[b] = k;
		}
	}
}

void expandBlossom(int b, bool endstage)
{
	for(int i = 0; i < blossomchilds[b].size(); i++)
	{
		int s = blossomchilds[b][i];
		blossomparent[s] = -1;
		if(s < nvertex && dualvar[s] == 0)
		{
			expandBlossom(s, endstage);
		}
		else
		{
			MyVector<int> vs = blossomLeaves(s);
			for(int j = 0; j < vs.size(); j++)
			{
				int v = vs[j];
				inblossom[v] = s;
			}
		}
	}
	if(!endstage && label[b] == 2)
	{
		if(labelend[b] < 0) throw "Assert Error";

		int entrychild = inblossom[endpoint[labelend[b] ^ 1]];
		int j = indexOf(blossomchilds[b], entrychild);
		int jstep, endptrick;
		if(j & 1)
		{
			j -= blossomchilds[b].size();;
			jstep = 1;
			endptrick = 0;
		}
		else
		{
			jstep = -1;
			endptrick = 1;
		}
		int p = labelend[b];
		while(j != 0)
		{
			label[endpoint[p ^ 1]] = 0;
			label[endpoint[blossomdps[b][j-endptrick]^endptrick]]=0;
			assignLabel(endpoint[p ^ 1], 2, p);
			allowedge[dd(blossomdps[b][j - endptrick],2)] = true; // row 391
			j += jstep;
			p = blossomdps[b][j-endptrick] ^ endptrick;
			allowedge[dd(p,2)] = true; // row 395
			j += jstep;
		}
		int bv = blossomchilds[b][j];
		label[endpoint[p^1]] = 2;
		label[bv] = 2;
		labelend[endpoint[p^1]] = p;
		labelend[bv] = p;
		bestedge[bv] = -1;
		j += jstep;
		while(blossomchilds[b][j] != entrychild)
		{
			bv = blossomchilds[b][j];
			if(label[bv] == 1)
			{
				j += jstep;
				continue;
			}
			MyVector<int> vs = blossomLeaves(bv);
			int v;
			for(int i = 0; i < vs.size(); i++)
			{
				v = vs[i];
				if (label[v] != 0) break;
			}
			if(label[v] != 0)
			{
				if(label[v] != 2) throw "Assert Error";
				if(inblossom[v] != bv) throw "Assert Error";
				label[v] = 0;
				label[endpoint[mate[blossombase[bv]]]] = 0;
				assignLabel(v, 2, labelend[v]);
			}
			j += jstep;
		}
	}

	label[b] = -1;
	labelend[b] = -1;
	blossomchilds[b] = MyVector<int>();
	blossomdps[b] = MyVector<int>();
	blossombase[b] = -1;
	blossombestedges[b] = MyVector<int>();
	bestedge[b] = -1;
	unusedblossoms.push_back(b);
}
void augmentBlossom(int b, int v)
{
	int t = v, p;
	while(blossomparent[t] != b)
	{
		t = blossomparent[t];
	}
	if(t >= nvertex)
	{
		augmentBlossom(t, v);
	}
	int i, j, jstep, endptrick;
	i = indexOf(blossomchilds[b], t);
	j = i;
	if(i & 1)
	{
		j -= blossomchilds[b].size();
		jstep = 1;
		endptrick = 0;
	}
	else
	{
		jstep = -1;
		endptrick = 1;
	}
	while(j != 0)
	{
		j += jstep;
		t = blossomchilds[b][j];
		p = blossomdps[b][j-endptrick]^endptrick;
		if(t >= nvertex)
		{
			augmentBlossom(t, endpoint[p]);
		}
		j+=jstep;
		t = blossomchilds[b][j];
		if(t >= nvertex)
		{
			augmentBlossom(t, endpoint[p^1]);
		}
		mate[endpoint[p]] = p ^ 1;
		mate[endpoint[p ^ 1]] = p;

	}
	MyVector<int> lst1, lst2;
	lst1 = skip(blossomchilds[b], i);
	lst2 = take(blossomchilds[b], i);
	for(int i = 0; i < lst2.size(); i++)
	{
		lst1.push_back(lst2[i]);
	}
	blossomchilds[b] = lst1;


	MyVector<int> lst3, lst4;
	lst3 = skip(blossomdps[b], i);
	lst4 = take(blossomdps[b], i);
	for(int i = 0; i < lst4.size(); i++)
	{
		lst3.push_back(lst4[i]);
	}
	blossomdps[b] = lst3;
	blossombase[b] = blossombase[blossomchilds[b][0]];
	if(blossombase[b] != v) 
		throw "Assert Error row 479";

}


void augmentMatching(int k)
{
	int v = edges[k][0];
	int w = edges[k][1];
	int wt = edges[k][2];

	MyVector<int> ss,ps;
	ss = MyVector<int>();
	ps = MyVector<int>();

	ss.push_back(v);
	ss.push_back(w);
	ps.push_back(2 * k + 1);
	ps.push_back(2 * k);

	for(int i = 0; i < 2; i++)
	{
		int s = ss[i];
		int p = ps[i];
		while(1)
		{
			int bs = inblossom[s];
			if(label[bs] != 1) throw "Assert Error";
			if(labelend[bs] != mate[blossombase[bs]]) throw "Assert Error";

			if(bs >= nvertex)
				augmentBlossom(bs, s);
			mate[s] = p;
			if(labelend[bs] == -1)
				break;

			int t = endpoint[labelend[bs]];
			int bt = inblossom[t];
			if(label[bt] != 2) throw "Assert Error";
			if(labelend[bt] < 0) throw "Assert Error";
			s = endpoint[labelend[bt]];
			int j = endpoint[labelend[bt] ^ 1];
			if(blossombase[bt] != t) throw "Assert Error";
			if(bt >= nvertex) 
				augmentBlossom(bt, j);
			mate[j] = labelend[bt];
			p = labelend[bt] ^ 1;
		}
	}
}

void verifyOptimum()
{
	int vdualoffset = 0;
	for(int k = 0; k < nedge; k++)
	{
		int i = edges[k][0];
		int j = edges[k][1];
		int wt = edges[k][2];
		int s = dualvar[i] + dualvar[j] - 2 * wt;
		MyVector<int> iblossoms, jblossoms;
		iblossoms = MyVector<int>();
		jblossoms = MyVector<int>();
		iblossoms.push_back(i);
		jblossoms.push_back(j);

		while(blossomparent[iblossoms[iblossoms.size() - 1]] != -1)
			iblossoms.push_back(blossomparent[iblossoms[iblossoms.size() - 1]]);
		while(blossomparent[jblossoms[jblossoms.size() - 1]] != -1)
			jblossoms.push_back(blossomparent[jblossoms[jblossoms.size() - 1]]);


		iblossoms.reverse();
		jblossoms.reverse();
		//std::reverse(iblossoms.begin(), iblossoms.end()); 
		//std::reverse(jblossoms.begin(), jblossoms.end()); 

		for(int i1 = 0; i1 < min(iblossoms.size(), jblossoms.size()); i1++)
		{
			int bi = iblossoms[i1];
			int bj = jblossoms[i1];
			if(bi != bj)
				break;
			s+=2 * dualvar[bi];
		}
		if(s < 0) 
			throw "Assert Error 553";
		if(dd(mate[i], 2) == k || dd(mate[j], 2) == k)
		{
			if(!(dd(mate[i], 2) == k && dd(mate[j], 2) == k)) 
				throw "Assert Error 555";
			if(s != 0) 
				throw "Assert Error 556";
		}
	}
	for(int v = 1; v < nvertex; v++)
		if(!(mate[v] >= 0 || dualvar[v] + vdualoffset == 0)) throw "Assert Error";

	for(int b = nvertex; b < 2 * nvertex; b++)
	{
		if(blossombase[b] >= 0 && dualvar[b] >0)
		{
			if(blossomdps[b].size() % 2 != 1) throw "Assert Error";			
			/*for p in blossomendps[b][1::2]:
        assert mate[endpoint[p]] == p ^ 1
        assert mate[endpoint[p ^ 1]] == p*/
		}
	}
}

void checkDelta2()
{
	for(int v = 0 ; v < nvertex; v++)
	{
		if(label[inblossom[v]] == 0)
		{
			int bd = 0;
			int bk = -1;
			for (int i = 0; i < neighbend[v].size(); i++)
			{
				int p = neighbend[v][i];
				int k = dd(p, 2);
				int w = endpoint[p];
				if(label[inblossom[w]] == 1)
				{
					int d = slack(k);
					if(bk == -1 || d < bd)
					{
						bk = k;
						bd = d;
					}
				}
			}
			if(!((bk == -1 && bestedge[v] == -1) || (bestedge[v] != -1 && bd == slack(bestedge[v])))) 
				throw "Assert Error";	
		}
	}
}

void checkDelta3()
{
	int bk = -1;
	int bd = -1;
	int tbk = -1;
	int tbd = -1;
	for(int b = 0; b < 2 * nvertex; b++)
	{
		if(blossomparent[b] == -1 && label[b] ==1)
		{
			MyVector<int> vs = blossomLeaves(b);
			for(int i1 = 0; i1 < vs.size(); i1++)
			{
				int v = vs[i1];
				for(int i2 = 0; i2 < neighbend[v].size(); i2++)
				{
					int p = neighbend[v][i2];
					int k = dd(p, 2);
					int w = endpoint[p];
					if(inblossom[w] != b && label[inblossom[w]] == 1)
					{
						int d = slack(k);
						if(bk == -1 || d < bd)
						{
							bk = k;
							bd = d;
						}
					}
				}
			}
			if(bestedge[b] != -1)
			{
				int i = edges[bestedge[b]][0];
				int j = edges[bestedge[b]][1];
				int wt = edges[bestedge[b]][2];
				if(!(inblossom[i] == b || inblossom[j] == b)) throw "Assert Error";			
				if(!(inblossom[i] != b || inblossom[j] != b)) throw "Assert Error";			
				if(!(label[inblossom[i]] == 1 && label[inblossom[j]] ==1)) throw "Assert Error";			
				if(tbk == -1 || slack(bestedge[b]) < tbd)
				{
					tbk = bestedge[b];
					tbd = slack(bestedge[b]);
				}
			}
		}
	}
	if(bd != tbd) throw "Assert Error";			
	
}
MyVector<int> MaxWeightedMatching(MyVector<EdmondsEdge> this_edges)
{
	edges = this_edges;
	nedge = this_edges.size();
	MyVector<int> empty_vector = MyVector<int>();

	if (edges.size() == 0) 
		return empty_vector;
	
	for(int i = 0; i < edges.size(); i++)
	{
		if(!(edges[i][0] >= 0 && edges[i][1]>=0 && edges[i][0] != edges[i][1])) throw "Assert Error";
		if(edges[i][0] >= nvertex) nvertex = edges[i][0] + 1;
		if(edges[i][1] >= nvertex) nvertex = edges[i][1] + 1;
	}
	
	for(int i = 0; i < edges.size(); i++)
	{
		max_weight = max (0, max(max_weight, edges[i][2]));
	}

	for(int i = 0; i < 2 * edges.size(); i++) 
	{ 		
		endpoint.push_back( edges[dd(i, 2)][i % 2]); 
	}

	for(int i = 0; i < nvertex; i++) 
	{
		neighbend.push_back(MyVector<int>());
	}

	for(int k = 0; k < edges.size(); k++)
	{
		int i = edges[k][0];
		int j = edges[k][1];

		neighbend[i].push_back(2 * k + 1);
		neighbend[j].push_back(2 * k);


		/*MyVector<int> first = neighbend[edges[k][0]];
		first.push_back(2 * k + 1);
		
		MyVector<int> second = neighbend[edges[k][1]];
		second.push_back(2 * k);*/
	}
	
	for(int i = 0; i < nvertex; i++)
	{
		mate.push_back(-1);
	}
	
	for(int i = 0; i < 2 * nvertex; i++)
	{
		label.push_back(0);
	}

	for(int i = 0; i < 2 * nvertex; i++)
	{
		labelend.push_back(-1);
	}
	
	for(int i = 0; i < nvertex; i++)
	{
		inblossom.push_back(i);
	}
	
	for(int i = 0; i < 2 * nvertex; i++)
	{
		blossomparent.push_back(-1);
	}
		
	for(int i = 0; i < 2 * nvertex; i++)
	{
		blossomchilds.push_back(MyVector<int>());
	}
		
	for(int i = 0; i < nvertex; i++)
	{
		blossombase.push_back(i);
	}
	for(int i = 0; i < nvertex; i++)
	{
		blossombase.push_back(-1);
	}
		
	for(int i = 0; i < 2 * nvertex; i++)
	{
		bestedge.push_back(-1);
	}

	for(int i = 0; i < 2 * nvertex; i++)
	{
		blossomdps.push_back(MyVector<int>());
	}

	for(int i = 0; i < 2 * nvertex; i++)
	{
		blossombestedges.push_back(MyVector<int>());
	}
		
	for(int i = nvertex; i < 2 * nvertex; i++)
	{
		unusedblossoms.push_back(i);
	}
	
	for(int i = 0; i < nvertex; i++)
	{
		dualvar.push_back(max_weight);
	}
	for(int i = 0; i < nvertex; i++)
	{
		dualvar.push_back(0);
	}
		
	for(int i = 0; i < nedge; i++)
	{
		allowedge.push_back(false);
	}
		
	
	for(int t = 0; t < nvertex; t++)
	{
		MyVector<int> label1 = MyVector<int>(2 * nvertex);
		for(int i = 0; i < label1.size(); i++)
		{
			label1[i] = 0;
		}
		label = label1;
	
		MyVector<int> label2 = MyVector<int>(2 * nvertex);
		for(int i = 0; i < label2.size(); i++)
		{
			label2[i] = -1;
		}
		bestedge = label2;

	
		for(int i = nvertex; i < 2 * nvertex; i++)
		{
			blossombestedges[i] = MyVector<int>();
		}

		for(int i = 0; i < nedge; i++)
		{
			allowedge[i] = false;
		}
	
		queue = MyVector<int>();
		for(int v = 0; v < nvertex; v++)
		{
			if (mate[v] == -1 && label[inblossom[v]] ==0)
				assignLabel(v, 1, -1);
		}
		int augmented = 0;
		while(1)
		{
			while(queue.size() > 0 && !augmented)
			{

				int v = queue[queue.size() - 1];
				queue.pop_back();

				if(label[inblossom[v]] != 1) throw "Assert Error";			

				for(int i = 0; i < neighbend[v].size(); i++)
				{
					int p = neighbend[v][i];
					int k = dd(p, 2);
					int w = endpoint[p];
					int kslack;//errore al secondo ciclo vale 0 a me e 10 a mudy... forse slack() e' sbagliata. Slack e' corretta, ma dualvar?? che fine ha fatto??

					if (inblossom[v] == inblossom[w])
						continue;
					if(!allowedge[k])
					{
						kslack = slack(k);
						if(kslack <= 0)
							allowedge[k] = true;
					}
					if(allowedge[k])
					{
						if(label[inblossom[w]] == 0)
							assignLabel(w,2,p^1);
						else if(label[inblossom[w]] == 1)
						{
							int base = scanBlossom(v, w); // breakpoint
							if(base >= 0)
								addBlossom(base, k);
							else
							{
								augmentMatching(k);
								augmented = 1;
								break;
							}
						}
						else if(label[w] == 0)
						{
							if(label[inblossom[w]] != 2) throw "Assert Error";			
							label[w] = 2;
							labelend[w] = p ^ 1;
						}
					}
					else if(label[inblossom[w]] == 1)
					{
						int b = inblossom[v];
						if(bestedge[b] == -1 || kslack < slack(bestedge[b]))
							bestedge[b] = k;
					}
					else if (label[w] == 0)
					{
						if (bestedge[w] == -1 || kslack < slack(bestedge[w]))
							bestedge[w] = k;
					}
				}

			}
			if(augmented)
				break;
			int deltatype = -1;
			int delta, deltaedge, deltablossom;
			if (CHECK_DELTA) // 730
			{
				checkDelta2();
				checkDelta3();
			}
		
			deltatype = 1;
			int _min = dualvar[0];
			for(int i = 0; i < nvertex; i++)
			{
				_min = min(_min, dualvar[i]);
			}
			delta = _min;
			for(int v = 0; v < nvertex; v++)
			{
				if(label[inblossom[v]] == 0 && bestedge[v] != -1)
				{
					int d = slack(bestedge[v]);
					if(deltatype == -1 || d < delta)
					{
						delta = d;
						deltatype = 2;
						deltaedge = bestedge[v];
					}
				}
			}
			for(int b = 0; b < 2 * nvertex; b++)
			{
				if(blossomparent[b] == -1 && label[b] == 1 && bestedge[b] != -1)
				{
					int kslack = slack(bestedge[b]);
					int d = dd(kslack, 2);
					if(deltatype == -1 || d <delta)
					{
						delta = d;
						deltatype = 3;
						deltaedge = bestedge[b];
					}
				}
			}
			for(int b = nvertex; b < 2 * nvertex; b++)
			{
				if(blossombase[b] >= 0 && blossomparent[b] == -1 && label[b] == 2 && 
					(deltatype == -1 || dualvar[b] < delta))
				{
					delta = dualvar[b];
					deltatype = 4;
					deltablossom = b;
				}
			}
			if(deltatype == -1)
			{
				deltatype = 1;
				int _min = dualvar[0];
				for(int i = 0; i < nvertex; i++)
				{
					_min = min(_min, dualvar[i]);
				}
				delta = max(_min, 0);
			}
			for(int v = 0; v < nvertex; v++)
			{
				if(label[inblossom[v]] == 1)
					dualvar[v] -= delta;
				else if(label[inblossom[v]] ==2)
					dualvar[v] += delta;
			}
			for(int b = nvertex; b < 2 * nvertex; b++)
			{
				if(blossombase[b] >= 0 && blossomparent[b] == -1)
				{
					if (label[b] ==1)
						dualvar[b] += delta;
					else if(label[b] ==2)
						dualvar[b] -= delta;
				}
			}
			if(deltatype == 1)
				break;
			else if(deltatype == 2)
			{
				allowedge[deltaedge] = true;
				int i = edges[deltaedge][0];
				int j = edges[deltaedge][1];
				int wt = edges[deltaedge][2];

				if(label[inblossom[i]] == 0)
				{
					int tmp = i;
					i = j;
					j = tmp;
				}
				if (label[inblossom[i]] != 1) 
					throw "Assert Error line 809";			
				queue.push_back(i);
			}
			else if(deltatype ==3)
			{
				allowedge[deltaedge] = true;
				int i = edges[deltaedge][0];
				int j = edges[deltaedge][1];
				int wt = edges[deltaedge][2];
				if(label[inblossom[i]] != 1) 
					throw "Assert Error line 815";
				queue.push_back(i);
			}
			else if(deltatype ==4)
				expandBlossom(deltablossom, false);
		}
		if(! augmented)
			break;
		for(int b = nvertex; b < 2 * nvertex; b++)
		{
			if(blossomparent[b] == -1 && blossombase[b] >= 0 && label[b] == 1 && dualvar[b] ==0)
				expandBlossom(b, true);
		}
	}
	if(CHECK_OPTIMUM)
		verifyOptimum();
	for(int v = 0; v < nvertex; v++)
	{
		if(mate[v] >=0)
			mate[v] = endpoint[mate[v]];
	}
	for(int v = 0; v < nvertex; v++)
		if(!(mate[v] == -1 || mate[mate[v]] == v)) throw "Assert Error";			

	return mate;
}
int _tmain(int argc, _TCHAR* argv[])
{
	MyVector<EdmondsEdge> test = MyVector<EdmondsEdge>();
	//test.push_back(EdmondsEdge(1,2,9));
	//test.push_back(EdmondsEdge(1,3,8));
	//test.push_back(EdmondsEdge(2,3,10));
	//test.push_back(EdmondsEdge(1,4,5));
	//test.push_back(EdmondsEdge(4,5,4));
	//test.push_back(EdmondsEdge(1,6,3));

	//MyVector<boolean> a = MyVector<boolean>();
	//a.push_back(true);
	////a.push_back(true);
	////a.push_back(false);

	//a[-2] = false;

	//auto b = a[-2];

	//test.push_back(EdmondsEdge(1,2,45));
	//test.push_back(EdmondsEdge(1,7,45));
	//test.push_back(EdmondsEdge(2,3,50));
	//test.push_back(EdmondsEdge(3,4,45));
	//test.push_back(EdmondsEdge(4,5,95));
	//test.push_back(EdmondsEdge(4,6,94));
	//test.push_back(EdmondsEdge(5,6,94));
	//test.push_back(EdmondsEdge(6,7,50));
	//test.push_back(EdmondsEdge(1,8,30));
	//test.push_back(EdmondsEdge(3,11,35));
	//test.push_back(EdmondsEdge(5,9,36));
	//test.push_back(EdmondsEdge(7,10,26));
	//test.push_back(EdmondsEdge(11,12,5));

	//test.push_back(EdmondsEdge(1,2,40));
	//test.push_back(EdmondsEdge(1,3,40));
	//test.push_back(EdmondsEdge(2,3,60));
	//test.push_back(EdmondsEdge(2,4,55));
	//test.push_back(EdmondsEdge(3,5,55));
	//test.push_back(EdmondsEdge(4,5,50));
	//test.push_back(EdmondsEdge(1,8,15));
	//test.push_back(EdmondsEdge(5,7,30));
	//test.push_back(EdmondsEdge(7,6,10));
	//test.push_back(EdmondsEdge(8,10,10));
	//test.push_back(EdmondsEdge(4,9,30));

	//test.push_back(EdmondsEdge(1,2,45));
	//test.push_back(EdmondsEdge(1,5,45));
	//test.push_back(EdmondsEdge(2,3,50));
	//test.push_back(EdmondsEdge(3,4,45));
	//test.push_back(EdmondsEdge(4,5,50));
	//test.push_back(EdmondsEdge(1,6,30));
	//test.push_back(EdmondsEdge(3,9,35));
	//test.push_back(EdmondsEdge(4,8,35));
	//test.push_back(EdmondsEdge(5,7,26));
	//test.push_back(EdmondsEdge(9,10,5));

	//test.push_back(EdmondsEdge(0,1,1));

	//test.push_back(EdmondsEdge(1,2,10));
	//test.push_back(EdmondsEdge(2,3,11));
	
	test.push_back(EdmondsEdge(1,2,5));
	test.push_back(EdmondsEdge(2,3,11));
	test.push_back(EdmondsEdge(3,4,5));


	auto res = MaxWeightedMatching(test);
	return 0;
}

